mod n_queen_problem;
mod serde_test;
mod test;

use std::mem::align_of_val;
use std::process::Output;
pub use test::*;

fn num_to_bit_str<T>(mut num: T) -> String
where
    T: Copy + std::ops::BitAnd<i32, Output = i32> + std::ops::ShrAssign<i32>,
{
    const MAX_ALIGN: usize = 256;
    const BYTE_ALIGN: usize = 8;
    let len = align_of_val(&num) * BYTE_ALIGN;
    let mut char_arr = [0 as u8; MAX_ALIGN];
    for i in 0..len {
        char_arr[MAX_ALIGN - i - 1] = ((num & 1) + 48) as u8;
        num >>= 1;
    }
    String::from_utf8_lossy(&char_arr[(MAX_ALIGN - len)..]).to_string()
}

struct FenwickTree {
    tree: Vec<i32>,
}

impl FenwickTree {
    fn bit_index(index: usize) -> usize {
        index & ((!(index as isize) + 1) as usize)
    }
    fn new(size: usize) -> FenwickTree {
        FenwickTree {
            tree: vec![0; size + 1],
        }
    }

    fn add(&mut self, mut index: usize, val: i32) {
        while index <= self.tree.len() {
            self.tree[index] += val;

            index += FenwickTree::bit_index(index);
        }
    }

    fn sum(&self, mut index: usize) -> i32 {
        if index <= 0 {
            return 0;
        }
        return self.tree[index] + self.sum(index - FenwickTree::bit_index(index));
    }
}

#[test]
fn test_fenwick_tree() {
    let len = 10_000usize;
    let mut tree = FenwickTree::new(len);
    for i in 1..len {
        tree.add(i, i as i32);
    }
    // tree.add(0, 1);
    println!("{}", tree.sum(5));
    // println!("{}", tree.sum(1000));

    let mut test_num = 100;
    let mut test_num_next = 0;
    for _ in 0..10 {
        test_num -= FenwickTree::bit_index(test_num);
        test_num_next += FenwickTree::bit_index(test_num_next);
        // println!("{}", test_num);
        println!("{}", test_num_next);
    }



}
